package com.zan.onelevel.level2;

import java.util.*;

/**
 * @Author Zan
 * @Date 2023/11/30 15:21
 * @Description :
 */
public class InterviewQuestion1 {

    public static void main(String[] args) {
        ListNode[] listNodes = initLinkedList();
        ListNode headA = listNodes[0];
        ListNode headB = listNodes[1];
        ListNode listNode = findFirstCommonNodeBySet(headA, headB);
        ListNode listNode2 = findFirstCommonNodeByViolence(headA, headB);
        System.out.println("当前公共结点的值为：" + listNode.data);
        System.out.println("当前公共结点的值为：" + listNode2.data);

    }

    /**
     * 1.暴力求解，循环遍历两个链表，判断结点相同
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode findFirstCommonNodeByViolence(ListNode headA, ListNode headB) {
        // 每一个结点进行比较，判断是否相同
        ListNode A = headA;
        ListNode B = headB;
        while (A != null) {
            while (B != null) {
                if (A == B) {
                    return A;
                }
                B = B.next;
            }
            B = headB;
            A = A.next;
        }
        return null;
    }

    /**
     * 2.使用Hash的方法
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode findFirstCommonNodeByMap(ListNode headA, ListNode headB) {
        Map<ListNode, Integer> hashMap = new HashMap<>();

        while (headA != null) {
            hashMap.put(headA, null);
            headA = headA.next;
        }

        while (headB != null) {
            if (hashMap.containsKey(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    /**
     * 3.使用集合的方法
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {
        List<ListNode> set = new ArrayList<>();
//        Set<ListNode> set = new HashSet<>();
        // 循环遍历head1，将head1所有元素存到set中
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }

        // 循环遍历head2，判断set集合链表是否包含head2
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    /**
     * 4.通过栈的方法
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
        Stack<ListNode> stackA = new Stack();
        Stack<ListNode> stackB = new Stack();
        while (headA != null) {
            stackA.push(headA); // 存入栈中
            headA = headA.next;
        }
        while (headB != null) {
            stackB.push(headB); // 存入栈中
            headB = headB.next;
        }

        ListNode preNode = null;
        while (stackB.size() > 0 && stackA.size() > 0) {
            // 由于存是从头存到底部，因此后面的结点都是相同的，当取出来是不一样的时候，说明从公共结点分隔出去了，到分岔口了，那就直接break即可
            if (stackA.peek() == stackB.peek()) { // peek表示查看此堆栈顶部的对象，但是不会删除，而pop是直接返回了，也就删除了
                preNode = stackA.pop();
                stackB.pop();
            } else {
                break;
            }
        }
        return preNode;
    }

    /**
     * 牛逼方法
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
        // 每一个结点进行比较，判断是否相同
        ListNode A = headA, B = headB;
        while (A != B) {
            if (A != null) {
                A = A.next;
            } else {
                A = headB;
            }

            if (B != null) {
                B = B.next;
            } else {
                B = headA;
            }
        }
        // 出循环的条件是 A结点 = B结点，因此获取到的就是公共结点
        return A;
    }

    /**
     * 简单构造两个链表
     *
     * @return
     */
    private static ListNode[] initLinkedList() {
        ListNode[] heads = new ListNode[2];
//        构造第一个链表交点之前的元素 1 ->2-> 3
        heads[0] = new ListNode(1);
        ListNode current1 = heads[0];
        current1.next = new ListNode(2);
        current1 = current1.next;
        current1.next = new ListNode(3);
        current1 = current1.next;
//        11->22
//        构造第二个链表交点之前的元素
        heads[1] = new ListNode(11);
        ListNode current2 = heads[1];
        current2.next = new ListNode(22);
        current2 = current2.next;
//        构造公共交点以及之后的元素

        ListNode node4 = new ListNode(4);
        current1.next = node4;
        current2.next = node4;
        ListNode node5 = new ListNode(5);
        node4.next = node5;


        ListNode node6 = new ListNode(6);
        node5.next = node6;

        return heads;
    }

}
